package tech

import (
	//"fmt"

	"slices"
	"ssp/set"
)

func (s *Solve) NWing(g *Grid) (used bool, results []*Result) {
	//fmt.Println("NWing")
	//g.printSimply()
	return g.nWing()
}

func (g *Grid) nWing() (used bool, results []*Result) {
	nwingStrongs := g.initNWingStrongs()
	for _, pivot := range g.getStableOrderedAllCells() {
		if ok, itemsss := g.findNWingChainsCell(pivot, nwingStrongs); ok {
			used = true
			for _, itemss := range itemsss {
				z := itemss[0][len(itemss[0])-1].cand
				zs := []*Cell{}
				for _, items := range itemss {
					for _, cell := range items[len(items)-2].group {
						if cell == nil {
							break
						}
						if !cell.cands.Has(z) {
							continue
						}
						zs = append(zs, cell)
					}
				}
				if ok, rmCells := g.canRemoveSeenCands(set.NewSet(z), zs); ok {
					used = true
					if CHANGE {
						removeCands(set.NewSet(z), rmCells)
					}
					//fmt.Println("zs:", z, zs)
					if OUTPUTRESULT {
						result := new(Result)
						result.addRemoved(set.NewSet(z), rmCells)
						result.setStrategyName("NWing")
						result.addHelpCells([]*Cell{pivot})
						cellss := [][]*Cell{}
						for _, items := range itemss {
							if len(items) != 4 {
								continue
							}
							cellss = append(cellss, items[2].getCells())
						}
						slices.SortFunc(cellss, compareCells)
						cellss = slices.CompactFunc(cellss, slices.Equal)
						for _, cells := range cellss {
							result.addHelpCells(cells)
						}

						results = append(results, result)
					}
					if !EXHAUSTIVE {
						return
					}
				}
			}
		}

	}
	return
}

func (g *Grid) initNWingStrongs() map[GroupItem][]GroupItem {
	ggs := map[GroupItem][]GroupItem{}
	for _, als := range g.getAllALS() {
		//fmt.Println(als)

		cands := unionCellCands(als)
		values := make([]GroupItem, cands.Count())
		for i, cand := range cands.GetList() {
			values[i] = GroupItem{cand: cand}
			copy(values[i].group[:], als)
		}
		for i, cand := range cands.GetList() {
			key := GroupItem{cand: cand}
			n := 0
			for _, cell := range als {
				if cell.cands.Has(cand) {
					key.group[n] = cell
					n++
				}
			}
			ggs[key] = append(ggs[key], values[:i]...)
			ggs[key] = append(ggs[key], values[i+1:]...)
		}
	}
	for _, v := range ggs {
		slices.SortFunc(v, func(a, b GroupItem) int {
			return len(a.getCells()) - len(b.getCells())
		})
	}
	return ggs
}

func (g *Grid) getStableOrderedAllCells() (cells []*Cell) {
	for _, cell := range g.allCells {
		if !cell.solved() {
			cells = append(cells, cell)
		}
	}

	slices.SortStableFunc(cells, func(a, b *Cell) int {
		return a.cands.Count() - b.cands.Count()
	})
	return
}

func (g *Grid) findNWingChainsCell(cell *Cell, nwingStrongs map[GroupItem][]GroupItem) (used bool, itemsss [][][]GroupItem) {
	heads := []GroupItem{}
	for _, cand := range cell.cands.GetList() {
		heads = append(heads, GroupItem{cand: cand, group: [9]*Cell{cell}})
	}
	return g.findNWingChains(heads, nwingStrongs)
}

func (g *Grid) findNWingChains(heads []GroupItem, nwingStrongs map[GroupItem][]GroupItem) (used bool, itemsss [][][]GroupItem) {
	n := len(heads)
	nodess := make([][]*ChainNode, n)

	for i, head := range heads {
		nodess[i] = g.travelNWingTo(head, nwingStrongs)
	}

	commonss := getForcingChainCommonNodes(nodess)
	//fmt.Println(g.alsStrongs)
	//fmt.Println("commonss", commonss)
	if len(commonss) == 0 {
		return
	}
	zs := make(map[GroupItem]bool, 0)
	for _, commons := range commonss {
		itemss := make([][]GroupItem, n)
		for i, common := range commons {
			itemss[i] = getItemsFromNode(common)
		}
		z := itemss[0][len(itemss[0])-2].cand
		cells := []*Cell{}
		for _, items := range itemss {
			for _, cell := range items[len(items)-2].group {
				if cell == nil {
					break
				}
				if !cell.cands.Has(z) {
					continue
				}
				cells = append(cells, cell)
			}
		}
		slices.SortFunc(cells, func(a, b *Cell) int {
			if a.rowNum-b.rowNum == 0 {
				return a.colNum - b.colNum
			} else {
				return a.rowNum - b.rowNum
			}
		})

		cells = slices.CompactFunc(cells, func(a, b *Cell) bool {
			return a == b
		})
		if len(cells) > 9 {
			continue
		}
		zgi := GroupItem{cand: z}
		for i, cell := range cells {
			zgi.group[i] = cell
		}
		if _, ok := zs[zgi]; !ok {
			zs[zgi] = true
			itemsss = append(itemsss, itemss)
		}
	}
	used = true
	return
}

func getForcingChainCommonNodes(nodess [][]*ChainNode) (commonss [][]*ChainNode) {
	itemNodes := map[GroupItem][]*ChainNode{}
	for _, nodes := range nodess {
		for _, node := range nodes {
			if _, ok := itemNodes[node.item]; !ok {
				itemNodes[node.item] = []*ChainNode{}
			}
			itemNodes[node.item] = append(itemNodes[node.item], node)
		}
	}
	for _, nodes := range itemNodes {
		if len(nodes) == len(nodess) {
			commonss = append(commonss, nodes)
		}
	}
	return
}

func getNWingStrongs(node *ChainNode, nwingStrongs map[GroupItem][]GroupItem) (strongs []GroupItem) {
	alss := nwingStrongs[node.item]
	for _, als := range alss {
		if isSameHouse(append(node.pre.item.getCells(), als.getCells()...)) {
			strongs = append(strongs, als)
		}
	}
	return
}

func (g *Grid) getNWingWeaks(node *ChainNode) (weaks []GroupItem) {
	//fmt.Println("getNWingWeaks", node.item)
	nodeCells := []*Cell{}
	for _, cell := range node.item.getCells() {
		if cell.cands.Has(node.item.cand) {
			nodeCells = append(nodeCells, cell)
		}
	}
	//nodeCells := node.item.getCells()

	if len(nodeCells) == 0 {
		return
	}

	houses := g.getSameHouses(nodeCells)

	for _, house := range houses {
		hCells := []*Cell{}
		for _, cell := range house.cells {
			//fmt.Println(cell, nodeCells, node.item.cand)
			if cell.solved() || cell.isMemberOf(nodeCells) ||
				!cell.cands.Has(node.item.cand) {
				continue
			}
			hCells = append(hCells, cell)
		}
		//fmt.Println(hCells)
		for n := 1; n <= len(hCells); n++ {
			for _, cells := range combine(hCells, n) {
				gi := GroupItem{cand: node.item.cand}
				copy(gi.group[:], cells)
				weaks = append(weaks, gi)
			}
		}
	}
	//compact weaks to remove the duplicated
	slices.SortStableFunc(weaks, compareGroupItem)
	weaks = slices.Compact(weaks)
	return weaks

}

func compareGroupItem(a, b GroupItem) int {
	return compareCells(a.getCells(), b.getCells())
}

func (g *Grid) travelNWingTo(head GroupItem, nwingStrongs map[GroupItem][]GroupItem) (weakNodes []*ChainNode) {
	cand := head.cand
	cell := head.group[0]
	levelNum := 1
	root := &ChainNode{nil, GroupItem{cand, [9]*Cell{cell, nil, nil}}}
	curLevel := []*ChainNode{root}
	usedWeaks := map[GroupItem]bool{}
	usedStrongs := map[GroupItem]bool{}
	usedWeaks[root.item] = true
	usedStrongs[root.item] = true
	strongFlag := false
	for levelNum < 4 {
		//fmt.Println(levelNum, strongFlag)
		nextLevel := []*ChainNode{}
		for _, node := range curLevel {
			if strongFlag {
				strongs := getNWingStrongs(node, nwingStrongs)
				//fmt.Println("strong from", node.item)
				for _, strong := range strongs {
					if usedStrongs[strong] {
						continue
					}
					//fmt.Println("strong to:  ", strong)
					next := &ChainNode{node, strong}
					nextLevel = append(nextLevel, next)
					usedStrongs[strong] = true
				}
			} else {
				weaks := g.getNWingWeaks(node)
				for _, weak := range weaks {
					if usedWeaks[weak] {
						continue
					}
					next := &ChainNode{node, weak}
					nextLevel = append(nextLevel, next)
					weakNodes = append(weakNodes, next)
					usedWeaks[weak] = true
				}
			}
		}
		if len(nextLevel) == 0 {
			break
		}
		//for _, node := range nextLevel {
		//	fmt.Println("  ", node.item)
		//}
		//fmt.Println()
		curLevel = nextLevel
		strongFlag = !strongFlag
		levelNum++
	}

	return
}

//*/
